The present invention relates to the field of computer operations on numbers in binary form, including addition, subtraction and comparisons. In particular, it relates to these operations when numbers are represented in redundant form.
In digital computations, the representation of numbers has a significant bearing upon the design of digital arithmetic circuits and therefore, upon their performance and complexity. Integer operands are represented in binary forms by ones and zeros in a base 2 number system. Three commonly used representation methods are called: sign-magnitude, one""s complement, and two""s complement.
FIG. 1a shows numbers represented in sign-magnitude. In sign-magnitude numbers, the most significant bit represents the sign (positive or negative) of the number. A sign-magnitude number can be negated by complementing the number""s sign bit. When adding two positive or two negative numbers, the operation is straightforward. But, when the signs of the operands are different, the number with the smaller magnitude should be subtracted from the number with the larger magnitude. This makes arithmetic operations on sign-magnitude numbers cumbersome. The circuit for performing arithmetic operations must include an adder circuit, a subtracter circuit and a comparator circuit. Because of the complexity, and because of a serial dependency upon a comparison to control the arithmetic circuitry, designers have proposed other representation methods.
FIG. 1b shows numbers represented in one""s complement. One way of determining the representation of a negative number in one""s complement is to subtract the magnitude of the number from 2nxe2x88x921 where n is the number of digits used in the representation. For example, if the word length is 4 bits, then 24xe2x88x921=15 is used, and the ones complement representation of xe2x88x927 is calculated as shown in 120 of FIG. 1b. 
A simpler way of determining the representation of a negative number in ones complement is to complement each bit of the corresponding positive number. This observation is key to simplifying subtraction for ones complement numbers. Since negating a number, B, is easily accomplished by digital circuitry, subtracting is accomplished through a combination of addition and negation:
Axe2x88x92B=A+(xe2x88x92B)
Since there are two ways to represent zero in the ones complement representation method, addition circuitry is still slightly complicated.
FIG. 1c shows numbers represented in twos complement. In twos complement representation, there is only one representation for zero. The representation of a negative number can be determined by subtracting the magnitude of the number from 2n where n is the number of digits used to represent the number. For example, to find the representation of xe2x88x927 in twos compliment, 24=16 is used, as in the calculation shown in 130 of FIG. 1c. 
FIG. 2 shows a 4-bit adder/subtracter for numbers represented in twos complement. A benefit of twos complement is that it reduces the complexity of the adder circuit. A twos complement adder/subtracter can be simplified by implementing twos complement negation as ones complement negation followed by incrementation.
In an addition/subtraction operation, carry signals propagate from right to left (less significant to more significant) until they reach a final destination, which can include the leftmost digit of a result. The time it takes for carry signals to propagate is directly related to the time it takes for a digital arithmetic circuit to produce a result of an operation. The circuit of FIG. 2 is referred to as a ripple adder. In a ripple adder, a carry signal at stage i+1 is given as a function of the inputs at the ith stage.
FIG. 3a shows a carry-lookahead adder circuit, which uses a circuit shown in FIG. 3b to propagate the carry signal. These circuits directly produce carry propagate and carry generate signals at each stage. FIG. 3c shows a set of alternative circuits used to propagate the carry signal according to Ling""s equations in an alternative carry-lookahead adder (Huey Ling, xe2x80x9cHigh-Speed Binary Adder,xe2x80x9d IBM J. Res. Develop., vol. 25, no. 3, May 1981).
The response time for a ripple adder with n stages is proportional to n, whereas the response time for a faster implementation such as a carry-lookahead adder is proportional to a logarithm of n.
In a system of numbers, where each number is assigned multiple binary representations, the numbers are said to be in redundant form. Further improvements in adder response times make use of numbers represented in redundant forms. For example, U.S. Pat. Nos. 4,890,127 and 5,815,420, use a signed-digit redundant representation form. Each digit is represented as a sign bit and a magnitude bit and can take on values of 1, 0, and xe2x88x921.
FIG. 4 shows a circuit for calculating the sign bit and magnitude bit for each digit in the result, Z, from the digits of the operands, X and Y (as described in FIG. 2 in U.S. Pat. No. 4,890,127). Negation is simple but calculations are somewhat complicated due to sign comparisons, and some calculations can generate new carries, which must be allowed to propagate. FIG. 5 shows a set of rules to determine intermediate carries and sums, that avoids generating problematic new carries but introduces some additional computational complexity (from N. Takagi et al, xe2x80x9cHigh speed VLSI multiplication algorithm with redundant binary addition tree,xe2x80x9d IEEE Trans. On Computes, 34 (September 1985) 789-796).
Current microprocessors make use of pipelining to reduce the cycle time and exploit parallelism within instruction streams. In order to make pipelining efficient, results from digital arithmetic circuitry are bypassed back to circuit inputs as operands for the next instruction in a pipeline. This technique is preferred over one of waiting until results are written back to a register file, and it provides for higher utilization of a pipeline""s parallelism.
Conversion from a redundant representation form to twos complement requires the propagation of carry signals. When results of a first operation are immediately required to perform a second operation, a conversion reduces the benefits of performing digital arithmetic in redundant form.
In U.S. Pat. No. 5,923,579, Widegen et al have shown a three-input comparator, where one of the inputs is an implicit constant. FIG. 6 shows a preferred embodiment of the comparator device consisting of a custom carry-save adder (CSA) structure and a carry-propagate circuit (CPC). The custom CSA uses two different bit cells depending upon whether that bit position in the constant input is a one or a zero, and the CPC employs a full carry-lookahead circuit to provide the comparison result as quickly as possible.